package leetcode_数组.matrix;

/**
 * 矩阵置零
 * 要分清元素是本来就是零，还是被变成零的
 * 先遍历数组，把元素为零的行号和列号记下来
 *      这里用两个 set 类型的数组
 * 然后再遍历，把需要置为零的元素变成零
 */
public class _73 {
    public void setZeroes(int[][] matrix) {
//        int m = matrix.length, n = matrix[0].length;
//        Set<Integer> row = new HashSet<>(), col = new HashSet<>();
//        for (int i = 0; i < m; i++) {
//            for (int j = 0; j < n; j++) {
//                if (matrix[i][j] == 0) {
//                    row.add(i);
//                    col.add(j);
//                }
//            }
//        }
//        for (int i = 0; i < m; i++) {
//            for (int j = 0; j < n; j++) {
//                if (row.contains(i) || col.contains(j)) {
//                    matrix[i][j] = 0;
//                }
//            }
//        }
        int m = matrix.length, n = matrix[0].length;
        int[][] tem = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    tem[i][j] = 1;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (tem[i][j] == 1) {
                    for (int k = 0; k < n; k++) {
                        matrix[i][k] = 0;
                    }
                    for (int k = 0; k < m; k++) {
                        matrix[k][j] = 0;
                    }
                }
            }
        }
    }

    /**
     * 最优解
     * 如果当前元素为 0 , 就把当前元素对应的行和列的第一个元素置为 0
     * 然后只需遍历第一行和第一列即可
     * 遇到的困难：
     *      在标记好第一行和第一列之后 , 把元素置零出现错误
     *      在置零的时候 , 把第一行和第一列都给算进去了 , 比如 matrix[0][0] 为零，则把第一行和第一列都置零了 ,
     *      这样做 matrix 都为零了
     * 解决: 设置两个布尔值变量，判断要不要把第一行和第一列都置零
     */
    public void setZeroes_perfect(int[][] matrix) {
        int r = matrix.length, c = matrix[0].length;
        boolean row0_flag = false, col0_flag = false;
        for (int i = 0; i < c; i++) {
            if (matrix[0][i] == 0) {
                row0_flag = true;
                break;
            }
        }
        for (int[] ints : matrix) {
            if (ints[0] == 0) {
                col0_flag = true;
                break;
            }
        }
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        for (int i = 1; i < r; i++) {
            if (matrix[i][0] == 0) {
                for (int j = 0; j < c; j++) {
                    matrix[i][j] = 0;
                }
            }
        }
        for (int i = 1; i < c; i++) {
            if (matrix[0][i] == 0) {
                for (int j = 0; j < r; j++) {
                    matrix[j][i] = 0;
                }
            }
        }
        if (row0_flag) {
            for (int i = 0; i < c; i++) {
                matrix[0][i] = 0;
            }
        }
        if (col0_flag) {
            for (int i = 0; i < r; i++) {
                matrix[i][0] = 0;
            }
        }
    }

    public void setZeroes_new(int[][] matrix) {
        // 使用第一行和第一列标识当前行和列是否要置为 0
        int m = matrix.length, n = matrix[0].length;
        boolean row = false, col = false;
        for (int[] ma : matrix)
            if (ma[0] == 0) {
                col = true;
                break;
            }
        for (int i = 0; i < n; i++)
            if (matrix[0][i] == 0) {
                row = true;
                break;
            }
        for (int i = 1; i < m; i++)
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        for (int i = 1; i < m; i++)
            for (int j = 1; j < n; j++) if (matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;
        if (row) for (int i = 0; i < n; i++) matrix[0][i] = 0;
        if (col) for (int i = 0; i < m; i++) matrix[i][0] = 0;
    }

}
